package leecode

var (
	index     []int
	temp      []int
	tempIndex []int
	ans       []int
)

func countSmaller(nums []int) []int {
	if len(nums) == 0 {
		return nums
	}
	index = make([]int, len(nums))
	tempIndex = make([]int, len(nums))
	ans = make([]int, len(nums))
	temp = make([]int, len(nums))
	for i := 0; i < len(nums); i++ {
		index[i] = i
	}
	left := 0
	right := len(nums) - 1
	process3(nums, left, right)
	return ans
}

func process3(nums []int, left, right int) {
	if left == right {
		return
	}
	mid := (left + right) >> 1
	process3(nums, left, mid)
	process3(nums, mid+1, right)
	merge3(nums, left, mid, right)
}

func merge3(nums []int, left, mid, right int) {
	help := make([]int, right-left+1)
	i := 0
	p1 := left
	p2 := mid + 1
	for p1 <= mid && p2 <= right {
		if nums[index[p1]] > nums[index[p2]] {
			help[i] = index[p2]
			ans[index[p1]] += i
			p1++
		} else {
			help = append(help, nums[index[p2]])
			p2++
			i++
		}
	}
	//检测数组左侧是否有未排序的数据
	for p1 <= mid {
		help = append(help, index[p1])
		ans[index[p1]] += i
		p1++
	}
	//检测数据右侧是否有未排序的数据
	for p2 <= right {
		help = append(help, index[p2])
		p2++
	}
	//修改nums数组中的值
	copy(index[left:right+1], help)
}
